//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
// Related Topics 栈 数组 单调栈 👍 1699 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

//Java：柱状图中最大的矩形
class LargestRectangleInHistogram{
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        // TO TEST
        int[] testArray = {2,1,5,6,2,3};
        int maxArea = solution.largestRectangleArea(testArray);
        System.out.println(maxArea);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
    //ss
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        int maxArea = 0;

        Deque<Integer> stack = new ArrayDeque<>(n);
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                //如果当前下标对应高度小于栈顶元素对应高度，栈顶元素出栈
                int curHeight = heights[stack.pollLast()];
                int curWidth;
                if (stack.isEmpty()) {
                    curWidth = i;
                } else {
                    curWidth = i - stack.peekLast() - 1;
                }
                maxArea = Math.max(maxArea, curHeight * curWidth);
            }
            //下标依次入栈
            stack.addLast(i);
        }

        while (!stack.isEmpty()) {
            int height = heights[stack.pollLast()];
            int width;
            if (stack.isEmpty()) {
                width = n;
            } else {
                width = n - stack.peekLast() - 1;
            }
            maxArea = Math.max(maxArea, width * height);
        }

        return maxArea;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
